๋ฌธ์
๋ฏธ์ธ๋จผ์ง๋ฅผ ์ ๊ฑฐํ๊ธฐ ์ํด ๊ตฌ์ฌ๊ณผ๋ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ฅผ ์ค์นํ๋ ค๊ณ ํ๋ค. ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ์ฑ๋ฅ์ ํ ์คํธํ๊ธฐ ์ํด ๊ตฌ์ฌ๊ณผ๋ ์ง์ ํฌ๊ธฐ๊ฐ RรC์ธ ๊ฒฉ์ํ์ผ๋ก ๋ํ๋๊ณ , 1ร1 ํฌ๊ธฐ์ ์นธ์ผ๋ก ๋๋ด๋ค. ๊ตฌ์ฌ๊ณผ๋ ๋ฐ์ด๋ ์ฝ๋ฉ ์ค๋ ฅ์ ์ด์ฉํด ๊ฐ ์นธ (r, c)์ ์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ ์ค์๊ฐ์ผ๋ก ๋ชจ๋ํฐ๋งํ๋ ์์คํ ์ ๊ฐ๋ฐํ๋ค. (r, c)๋ rํ c์ด์ ์๋ฏธํ๋ค.
๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ ํญ์ 1๋ฒ ์ด์ ์ค์น๋์ด ์๊ณ , ํฌ๊ธฐ๋ ๋ ํ์ ์ฐจ์งํ๋ค. ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์ค์น๋์ด ์์ง ์์ ์นธ์๋ ๋ฏธ์ธ๋จผ์ง๊ฐ ์๊ณ , (r, c)์ ์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ Ar,c์ด๋ค.
1์ด ๋์ ์๋ ์ ํ ์ผ์ด ์์๋๋ก ์ผ์ด๋๋ค.
-
๋ฏธ์ธ๋จผ์ง๊ฐ ํ์ฐ๋๋ค. ํ์ฐ์ ๋ฏธ์ธ๋จผ์ง๊ฐ ์๋ ๋ชจ๋ ์นธ์์ ๋์์ ์ผ์ด๋๋ค.
- (r, c)์ ์๋ ๋ฏธ์ธ๋จผ์ง๋ ์ธ์ ํ ๋ค ๋ฐฉํฅ์ผ๋ก ํ์ฐ๋๋ค.
- ์ธ์ ํ ๋ฐฉํฅ์ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์๊ฑฐ๋, ์นธ์ด ์์ผ๋ฉด ๊ทธ ๋ฐฉํฅ์ผ๋ก๋ ํ์ฐ์ด ์ผ์ด๋์ง ์๋๋ค.
- ํ์ฐ๋๋ ์์ Ar,c/5์ด๊ณ ์์์ ์ ๋ฒ๋ฆฐ๋ค.
- (r, c)์ ๋จ์ ๋ฏธ์ธ๋จผ์ง์ ์์ Ar,c - (Ar,c/5)ร(ํ์ฐ๋ ๋ฐฉํฅ์ ๊ฐ์) ์ด๋ค.
-
๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์๋ํ๋ค.
- ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์์๋ ๋ฐ๋์ด ๋์จ๋ค.
- ์์ชฝ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ๋ฐ๋์ ๋ฐ์๊ณ๋ฐฉํฅ์ผ๋ก ์ํํ๊ณ , ์๋์ชฝ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ๋ฐ๋์ ์๊ณ๋ฐฉํฅ์ผ๋ก ์ํํ๋ค.
- ๋ฐ๋์ด ๋ถ๋ฉด ๋ฏธ์ธ๋จผ์ง๊ฐ ๋ฐ๋์ ๋ฐฉํฅ๋๋ก ๋ชจ๋ ํ ์นธ์ฉ ์ด๋ํ๋ค.
- ๊ณต๊ธฐ์ฒญ์ ๊ธฐ์์ ๋ถ๋ ๋ฐ๋์ ๋ฏธ์ธ๋จผ์ง๊ฐ ์๋ ๋ฐ๋์ด๊ณ , ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ก ๋ค์ด๊ฐ ๋ฏธ์ธ๋จผ์ง๋ ๋ชจ๋ ์ ํ๋๋ค.
๋ค์์ ํ์ฐ์ ์์์ด๋ค.
- ์ผ์ชฝ๊ณผ ์ค๋ฅธ์ชฝ์ ์นธ์ด ์๊ธฐ ๋๋ฌธ์, ๋ ๋ฐฉํฅ์ผ๋ก๋ง ํ์ฐ์ด ์ผ์ด๋ฌ๋ค.
- ์ธ์ ํ ๋ค ๋ฐฉํฅ์ผ๋ก ๋ชจ๋ ํ์ฐ์ด ์ผ์ด๋๋ค.
- ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์๋ ์นธ์ผ๋ก๋ ํ์ฐ์ด ์ผ์ด๋์ง ์๋๋ค.
๊ณต๊ธฐ์ฒญ์ ๊ธฐ์ ๋ฐ๋์ ๋ค์๊ณผ ๊ฐ์ ๋ฐฉํฅ์ผ๋ก ์ํํ๋ค.
๋ฐฉ์ ์ ๋ณด๊ฐ ์ฃผ์ด์ก์ ๋, T์ด๊ฐ ์ง๋ ํ ๊ตฌ์ฌ๊ณผ์ ๋ฐฉ์ ๋จ์์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ ๊ตฌํด๋ณด์.
์ , ์ถ๋ ฅ
์ ๋ ฅ
- ์ฒซ์งธ ์ค์ R, C, T (6 โค R, C โค 50, 1 โค T โค 1,000) ๊ฐ ์ฃผ์ด์ง๋ค.
- ๋์งธ ์ค๋ถํฐ R๊ฐ์ ์ค์ Ar,c (-1 โค Ar,c โค 1,000)๊ฐ ์ฃผ์ด์ง๋ค. ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๊ฐ ์ค์น๋ ๊ณณ์ Ar,c๊ฐ -1์ด๊ณ , ๋๋จธ์ง ๊ฐ์ ๋ฏธ์ธ๋จผ์ง์ ์์ด๋ค. -1์ 2๋ฒ ์์๋๋ก ๋ถ์ด์ ธ ์๊ณ , ๊ฐ์ฅ ์ ํ, ์๋ซ ํ๊ณผ ๋ ์นธ์ด์ ๋จ์ด์ ธ ์๋ค.
์ถ๋ ฅ
- ์ฒซ์งธ ์ค์ T์ด๊ฐ ์ง๋ ํ ๊ตฌ์ฌ๊ณผ ๋ฐฉ์ ๋จ์์๋ ๋ฏธ์ธ๋จผ์ง์ ์์ ์ถ๋ ฅํ๋ค.
๐ Logic
class Room {
Queue<Pair> dustQueue = new LinkedList<>();
int[][] room;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
int R, C;
int cleaner1X, cleaner2X;
...
}
- ๋ฏธ์ธ ๋จผ์ง์ ๊ณต๊ธฐ์ฒญ์ ๊ธฐ ์ ๋ณด๋ฅผ ์ ์ฅํ๋ ํด๋์ค
public int goodByeFineDust(int time) {
while(time > 0) {
spreadDust();
runCleaner();
time--;
}
return countDust();
}
- ์ฝ๋๋ ๋จผ์ง๋ฅผ ํ์ฐ์ํค๊ณ , ๊ณต๊ธฐ์ฒญ์ ๊ธฐ๋ฅผ ๋์์ํจ๋ค. ์ ํด์ง ์๊ฐ์ด ๊ฒฝ๊ณผํ ํ, ์ ์ฒด ๋ฏธ์ธ ๋จผ์ง๋ฅผ ๋ฐํํ๋ค.
private void spreadDust() {...}
Queue์ ์ ์ฅํ๊ณ ์๋ ๋ฏธ์ธ ๋จผ์ง ์ขํ๋ฅผ ์ด์ฉํด ๋ฏธ์ธ ๋จผ์ง๋ฅผ ํ์ฐ์ํจ๋ค.- ์ด๋ ์
๋ฐ์ดํธํ ๋ฏธ์ธ ๋จผ์ง ์ ๋ณด๋ฅผ
int[][] tmp์ ์ ์ฅํ๊ณ , ํ์ฐ์ด ๋๋ ์ดํroom์ ์ ๋ฐ์ดํธํ๋ค.
private void runCleaner() {...}
- ๊ณต๊ธฐ ์ฒญ์ ๊ธฐ์ ๋ฐ๋ ๋ฐฉํฅ์ ๋ฐ๋ผ ์์ฐจ์ ์ผ๋ก ๋ฏธ์ธ ๋จผ์ง๋ฅผ ์ด๋์ํจ๋ค.
- ๊ณต๊ธฐ ์ฒญ์ ๊ธฐ ๋ฐ๋ก ์ ์ขํ๋ ํญ์
0์ผ๋ก ์ ๋ฐ์ดํธํ๋ค.
๐ CODE
์ฝ๋ ๋ณด๊ธฐ/์ ๊ธฐ๐ซ
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
class Room {
Queue<Pair> dustQueue = new LinkedList<>();
int[][] room;
int[] rangeX = { -1, 0, 1, 0 };
int[] rangeY = { 0, 1, 0, -1 };
int R, C;
int cleaner1X, cleaner2X;
public Room (int R, int C) {
this.R = R;
this.C = C;
room = new int[R][C];
}
public int goodByeFineDust(int time) {
while(time > 0) {
spreadDust();
runCleaner();
time--;
}
return countDust();
}
private void spreadDust() {
int[][] tmp = new int[R][C];
while(!dustQueue.isEmpty()) {
Pair dust = dustQueue.poll();
int divDust = room[dust.x][dust.y] / 5;
int checkSpread = 0;
for (int i = 0; i < 4; i++) {
int nx = dust.x + rangeX[i];
int ny = dust.y + rangeY[i];
if (nx < 0 || nx > R - 1 || ny < 0 || ny > C - 1) continue;
if (room[nx][ny] == -1) continue;
tmp[nx][ny] += divDust;
checkSpread++;
}
tmp[dust.x][dust.y] = tmp[dust.x][dust.y] + room[dust.x][dust.y] - (divDust * checkSpread);
}
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (room[i][j] == -1) continue;
room[i][j] = tmp[i][j];
}
}
}
private void runCleaner() {
int i = 0;
for (i = cleaner1X - 2; i >= 0; i--) {
room[i + 1][0] = room[i][0];
}
for (i = 1; i < C; i++) {
room[0][i - 1] = room[0][i];
}
for (i = 1; i <= cleaner1X; i++) {
room[i - 1][C - 1] = room[i][C - 1];
}
for (i = C - 2; i > 0; i--) {
room[cleaner1X][i + 1] = room[cleaner1X][i];
}
for (i = cleaner2X + 2; i < R; i++) {
room[i - 1][0] = room[i][0];
}
for (i = 1; i < C; i++) {
room[R - 1][i - 1] = room[R - 1][i];
}
for (i = R - 2; i >= cleaner2X; i--) {
room[i + 1][C - 1] = room[i][C - 1];
}
for (i = C - 2; i > 0; i--) {
room[cleaner2X][i + 1] = room[cleaner2X][i];
}
room[cleaner1X][1] = room[cleaner2X][1] = 0;
for (i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (room[i][j] > 0) dustQueue.add(new Pair(i, j));
}
}
}
private int countDust() {
int count = 0;
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (room[i][j] > 0) count += room[i][j];
}
}
return count;
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int R = line[0], C = line[1], T = line[2];
Room dirtyRoom = new Room(R, C);
for (int i = 0; i < R; i++) {
dirtyRoom.room[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
if (dirtyRoom.room[i][0] == -1 && dirtyRoom.cleaner1X == 0) {
dirtyRoom.cleaner1X = i;
dirtyRoom.cleaner2X = i+1;
}
for (int j = 0; j < C; j++) {
if (dirtyRoom.room[i][j] > 0) dirtyRoom.dustQueue.add(new Pair(i, j));
}
}
br.close();
System.out.println(dirtyRoom.goodByeFineDust(T));
}
}
โ๏ธ Review
- ๋ฏธ์ธ๋จผ์ง๋ฅผ ํ์ฐ์ํค๋ ๋ฐฉ๋ฒ์์ ์๊ฐ์ ๋ง์ด ๋บ๊ฒผ๋ค. ๊ฒฐ๋ก ์ ์ผ๋ก๋ ์ถ๊ฐ์ ์ธ ๋ฐฐ์ด์ ๋๊ณ , ๋ฏธ์ธ๋จผ์ง ํ์ฐ ์ ๋ณด๋ฅผ ์ ์ฅํด๋๊ณ ,
room์ ์ ๋ฐ์ดํธํ๋ ๋ฐฉ์์ด ํ์ํ๋ค. - ์๋ฎฌ๋ ์ด์ ์ ๋จ์ํ ๋ฏ ํ๋ฉด์ ๋ง์ ์ฝ๋๋์ ์๊ตฌํ๋ ๊ฒ ๊ฐ๋ค...
๐ ์ถ์ฒ
Baekjoon : https://www.acmicpc.net/problem/17144